package innersort.swap;

import innersort.speed.SortStrategy;

import java.util.Arrays;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-03 18:58
 * @ Description :
 */
public class QuickSort implements SortStrategy
{
    public static void main(String[] args)
    {
        int[] array = {-9, 78, 0, 23, -567, 70, -1, 900,456};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));

    }

    @Override
    public void sort(int[] array)
    {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int left, int right)
    {
        int leftIndex = left;
        int rightIndex = right;
        int pivot = array[(left + right) / 2];

        int temp = 0;

        //对key两边的值操作，使得左边的 <= key ; 右边的 >= key
        while (leftIndex < rightIndex)
        {
            //找到左边第一个大于pivot的值
            while (array[leftIndex] < pivot)
            {
                leftIndex++;
            }
            //找到右边第一个小于pivot的值
            while (array[rightIndex] > pivot)
            {
                rightIndex--;
            }

            //如果左右指针遍历到了pivot
            if (leftIndex >= rightIndex)
            {
                //pivot左右分别为小与pivot和大于pivot的数
                break;
            }
            //对找到未分类的值,交换
            temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;

            //防止相等的值死循环
            if (array[leftIndex] == pivot)
            {
                rightIndex--;
            }
            if (array[rightIndex] == pivot)
            {
                leftIndex++;
            }

        }

        if (leftIndex == rightIndex)
        {
            leftIndex++;
            rightIndex--;
        }

        //递归终止条件是: rightIndex <= left && leftIndex >= right

        //左递归
        if (left < rightIndex)
        {
            quickSort(array, left, rightIndex);
        }
        //右递归
        if (right > leftIndex)
        {
            quickSort(array, leftIndex, right);
        }
    }
}
